package LeetCodeSection;/*
 *
 *@author:    Xavier
 *@data:      2023 - 08 - 20
 *@time:      14:24
 *
 */

//4. 平衡二叉树
//https://leetcode.cn/problems/balanced-binary-tree/
public class BalancedBinaryTree {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;

        int leftHight = maxDepth(root.left);
        int rightHight = maxDepth(root.right);

        return Math.abs(leftHight - rightHight) < 2
                && isBalanced(root.left)
                && isBalanced(root.right);
    }

    public static int maxDepth(TreeNode root){
        if (root == null) return 0;
        int leftH = maxDepth(root.left);
        int rightH = maxDepth(root.right);

        return (leftH > rightH ? leftH : rightH) + 1;
    }

        public boolean isBalanced2(TreeNode root) {
            if (root == null) return true;

            return maxDepth2(root) >= 0;
        }
        public static int maxDepth2(TreeNode root){
            if (root == null) return 0;
            int leftH = maxDepth(root.left);
            int rightH = maxDepth(root.right);

            if (leftH >= 0 && rightH >= 0
            && Math.abs(leftH - rightH) <= 1) {
                return Math.max(leftH,rightH) + 1;
            }else {
                return -1;
            }
        }
    }
}
